package algorithm;

@SuppressWarnings("ALL")
public class T00092 {
    public static void main(String[] args) {
        ListNode head = build(1,2,3,4,5);
//        print(head);
        print(new Solution().reverseBetween(head, 3,4));
    }

    static void print(ListNode head) {
        if(head == null)
            return;
        ListNode c = head;
        while(true) {
            System.out.print(c.val);
            if((c = c.next) == null)
                break;
            System.out.print(" -> ");
        }
        System.out.println();
    }

    static ListNode build(int... arr) {
        ListNode head = null;
        for (int i = arr.length - 1; i >= 0; i --) {
            ListNode t = new ListNode(arr[i]);
            t.next = head;
            head = t;
        }
        return head;
    }
    static class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            if (head.next == null || left == right) {
                return head;
            }
            if (left == 1) {
                return reverseN(head, right - left + 1);
            }
            ListNode p = head;
            int n = left;
            while (n -- > 2) {
                p = p.next;
            }
            p.next = reverseN(p.next, right - left + 1);
            return head;
        }

        public ListNode reverseN(ListNode head, int n) {
            if (head == null) {
                return head;
            }
            ListNode pre = null, cur = head, tail = head, next = head.next;
            while (n -- > 0 && cur != null) {
                cur.next = pre;
                pre = cur;
                cur = next;
                if (next != null) {
                    next = next.next;
                }
            }
            tail.next = cur;
            return pre;
        }
    }
    
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}
